#include "tree.h"

Tree::Tree() {
    this->root = nullptr;
    this->is_binary = false;
}

TreeNode* BuildBinaryTree(QString str, TreeNode *parent) {
    if (0 == str.length() || str.at(0).toLatin1() == '^') {
        return nullptr;
    }
    TreeNode *root = new TreeNode;
    root->val = str.at(0).toLatin1();
    root->parent = parent;
    str = str.mid(2, str.length() - 3);

    // 用于括号匹配的栈
    int parenthesesCnt = 0;
    QString leftTree = "", rightTree = "";
    for (int i = 0; i <= str.length(); i++) {
        if (i == str.length()) {
            leftTree = str;
            break;
        }
        if (str[i] == '(') {
            parenthesesCnt++;
        }
        else if (str[i] == ')') {
            parenthesesCnt--;
        }
        else if (str[i] == ',') {
            if (parenthesesCnt == 0) {
                leftTree = str.left(i);
                rightTree = str.right(str.length() - i - 1);
                break;
            }
        }
    }
    root->lrchild.first = BuildBinaryTree(leftTree, root);
    root->lrchild.second = BuildBinaryTree(rightTree, root);
    return root;
}

TreeNode* BuildNormalTree(QString str, TreeNode* parent) {
    if (0 == str.length()) {
        return nullptr;
    }
    TreeNode *root = new TreeNode;
    root->val = str.at(0).toLatin1();
    root->parent = parent;
    str = str.mid(2, str.length() - 3);

    // 用于括号匹配的栈
    int parenthesesCnt = 0;
    QString tmp = "";
    if (str.length() != 0) {
        for (int i = 0; i <= str.length(); i++) {
            if (i == str.length()) {
                if (tmp.at(0).toLatin1() != '^') {
                    root->children.PushBack(BuildNormalTree(tmp, root));
                }
                break;
            }
            if (str[i] == '(') {
                parenthesesCnt++;
            }
            else if (str[i] == ')') {
                parenthesesCnt--;
            }
            if (str[i] == ',' && parenthesesCnt == 0) {
                if (tmp.at(0).toLatin1() != '^') {
                    root->children.PushBack(BuildNormalTree(tmp, root));
                }
                tmp = "";
            }
            else {
                tmp.push_back(str[i]);
            }
        }
    }
    return root;
}

Tree::Tree(bool is_binary, QString str) {
    this->is_binary = is_binary;
    if (is_binary) {
        this->root = BuildBinaryTree(str, nullptr);
    }
    else {
        this->root = BuildNormalTree(str, nullptr);
    }
}

void DestoryBinaryTree(TreeNode *root) {
    if (root == nullptr) {
        return;
    }
    if (root->lrchild.first != nullptr) {
        DestoryBinaryTree(root->lrchild.first);
    }
    if (root->lrchild.second != nullptr) {
        DestoryBinaryTree(root->lrchild.second);
    }
    delete root;
}

void DestoryNormalTree(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    for (int i = 0; i < root->children.Size(); i++) {
        DestoryNormalTree(root->children[i]);
    }
    delete root;
}

Tree::~Tree() {
    if (is_binary) {
        DestoryBinaryTree(this->root);
    } else {
        DestoryNormalTree(this->root);
    }
}

QString BinaryTree2ParenthesisString(TreeNode *root) {
    if (root == nullptr) {
        return "^";
    }
    if (root->lrchild.first == nullptr && root->lrchild.second == nullptr) {
        return QString(root->val);
    }
    return QString(root->val) + "(" + BinaryTree2ParenthesisString(root->lrchild.first) + "," + BinaryTree2ParenthesisString(root->lrchild.second) + ")";
}

QString NormalTree2ParenthesisString(TreeNode *root) {
    if (root == nullptr) {
        return "^";
    }
    if (root->children.Size() == 0) {
        return QString(root->val);
    }
    QString res = QString(root->val) + "(";
    for (int i = 0; i < root->children.Size(); i++) {
        if (i != 0) {
            res += ",";
        }
        res += NormalTree2ParenthesisString(root->children[i]);
    }
    return res + ")";
}

QString Tree::ToParenthesisString() const {
    if (is_binary) {
        return BinaryTree2ParenthesisString(this->root);
    }
    else {
        return NormalTree2ParenthesisString(this->root);
    }
}

int GetTreeDepth(TreeNode *root, int depth) {
    int x = depth;
    if (root->lrchild.first != nullptr) {
        x = qMax(x, GetTreeDepth(root->lrchild.first, depth + 1));
    }
    if (root->lrchild.second != nullptr) {
        x = qMax(x, GetTreeDepth(root->lrchild.second, depth + 1));
    }
    return x;
}

int Tree::GetDepth() const {
    if (!this->is_binary) {
        return -1;
    }
    return GetTreeDepth(this->root, 1);
}
